package Sort;

/**
 * @author chetaifu
 */
public class QuickSort3Ways {
    public static void sort(Comparable[] arr){
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(Comparable[] arr, int low, int high){
        if(low >= high){
            return;
        }

        // 插入排序优化
        if(high - low <= 15){
            insertSort(arr, low, high);
            return;
        }

        swap(arr, low, (int) (Math.random() * (high - low + 1) + low));

        Comparable v = arr[low];

        // arr[low + 1 ... left] < v
        int left = low;
        // arr[right ... high] > v
        int right = high;
        // arr[left + 1 ... i) == v
        int i = low + 1;
        while(i < right){
            if(arr[i].compareTo(v) < 0){
                swap(arr, i, left + 1);
                i ++;
                left ++;
            }else if (arr[i].compareTo(v) > 0) {
                swap(arr, i, right - 1);
                right --;
            }else{
                i ++;
            }
        }
        swap(arr, low, left);
        sort(arr, low, left - 1);
        sort(arr, right, high);

    }

    private static void swap(Object[] arr, int i, int j){
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    private static void insertSort(Comparable[] array, int low, int high){
        Comparable tmp;
        int j;
        for (int i = low + 1; i <= high ; i++) {
            tmp = array[i];
            for (j = i - 1; j >= low && array[j].compareTo(tmp) > 0; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = tmp;
        }
    }
}
